/**
 * @brief  LRU Least Recent Used. 
 *
 * @author Huang RuiGuang
 * @date 2008/12/1
 *
 * Herm library
 * Copyright (c) 2008 by Huang RuiGuang(daemon.huang@gmail.com)
 *
 * Permission to use, copy, modify, distribute and sell this software.
 */

#ifndef __HERM_BASE_CONTAINER_LRU_H__
#define __HERM_BASE_CONTAINER_LRU_H__

#include <map>
#include "herm/export_symbols.h"
#include "herm/base/utils/types.h"
#include "private/list.h"
#include "allocator.h"

namespace herm{

template <class DataKey>
class HERM_API Lru
{
public:
    Lru(size_t maxSize)
	{
		m_maxSize = maxSize;
	}
    /**
     * @brief Update the access node.
     * @return if is true, removing a key by \aremovingKey.
	 */
    bool Update(DataKey key, DataKey& removingKey)
	{
		bool isRemoving = false;
	//	removingKey = 0;
		typename Key2Node::const_iterator it = m_key2Node.find(key);
		if (it != m_key2Node.end())
		{
			KeyNode* node = it->second;
			// If the update node is back in the update list, do nothing
			if (!m_updateList.IsBack(node))
			{
				m_updateList.Erase(node);
				m_updateList.PushBack(node);
			}
		}
		else
		{
			if (m_key2Node.size() >= m_maxSize)
			{
				KeyNode* node = m_updateList.PopFront();
				if (node)
				{
					isRemoving = true;
					removingKey = node->key;
					m_key2Node.erase(node->key);

					m_nodeAlloc.Free(node);
				}
			}

			KeyNode* node = m_nodeAlloc.Malloc();
			node->key = key;
			m_updateList.PushBack(node);
			m_key2Node.insert(std::make_pair(key, node));
		}

		return isRemoving;
	}
private:
    struct KeyNode
    {
        DataKey key;
        KeyNode* pre;
        KeyNode* next;
    };

    size_t m_maxSize;
    herm::LiteAllocator<KeyNode> m_nodeAlloc;
	typedef std::map<DataKey, KeyNode*> Key2Node;
    Key2Node m_key2Node;
    Private::DeList<KeyNode> m_updateList;
};
}

#endif

